In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L.
Contents |
Given of a monoid M, one may define sets that consist of formal left or right inverses of elements in S. These are called quotients, and one may define right or left quotients, depending on which side one is concatenating. Thus, the right quotient of S by an element is the set
Similarly, the left quotient is
The syntactic quotient induces an equivalence relation on M, called the syntactic relation, or syntactic equivalence or syntactic congruence (induced by S). The right syntactic equivalence is the equivalence relation
Similarly, the left syntactic relation is
A double-sided congruence may be defined as
The syntactic quotient is compatible with concatenation in the monoid, in that one has
for all (and similarly for the left quotient). Thus, the syntactic quotient is a monoid morphism, and induces a quotient monoid
It can be shown that the syntactic monoid of S is the smallest monoid that recognizes S ; that is, M(S) recognizes S, and for every monoid N recognizing S, M(S) is a quotient of a submonoid of N. The syntactic monoid of S is also the transition monoid of the minimal automaton of S.
Equivalently, a language L is recognizable if and only if the family of quotients
is finite. The proof showing equivalence is quite easy. Assume that a string x is recognizable by a deterministic finite automaton, with the final state of the machine being f. If y is another string recognized by the machine, also terminating in the same final state f, then clearly one has . Thus, the number of elements in is just exactly equal to the number of final states of the automaton. Assume the converse: that the number of elements in is finite. One can then construct an automaton where so that is the set of states, is the set of final states, the language L is the initial state, and the transition function is given by . Clearly, this automaton recognizes L. Thus, a language L is recognizable if and only if the set is finite.
Given a regular expression E representing S, it is easy to compute the syntactic monoid of S.